107. Binary Tree Level Order Traversal II

2018-03-06

题目描述：

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

思路：

使用队列逐层遍历，存到res，不过这道题是反向存储，所以每层得到的List就存入res的起始位置，这样就倒序了
这里有两种集合可以实现插入起始位置：
若使用ArrayList，使用add(index,ArrayList)方法
若使用LinkedList，使用addFirst(ArrayList)方法

PS:
这里遇到的一个问题就是返回值是List<List<Integer>>这样的集合嵌套形式，参见我的另一篇Java集合嵌套的笔记。

题解：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<List<Integer>> res=new ArrayList<List<Integer>>();
        if(root==null)
            return res;
        
        LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        int count=1;
        
        ArrayList<Integer> middleList=new ArrayList<Integer>();
        TreeNode tmp=null;
        while(!queue.isEmpty()){
            tmp=queue.poll();
            count--;
            middleList.add(tmp.val);
            if(tmp.left!=null){
                queue.add(tmp.left);
                //count++;
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
                //count++;
            }
           if(count==0){
                res.add(0,middleList); //insert one by one from the beginning
                middleList=new ArrayList<Integer>(); //这里注意不能赋值为null
                count=queue.size();
            }
            
        }
        return res;
    }
}